package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

/*
112. 路径总和
 */
public class Of20210313LeetCode112 {
    /*
    给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     */
    public static void main(String[] args) {
        TreeNode node = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))
                , null), new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
        System.out.println(hasPathSum(node, 28));
    }

    /*
    递归
     */
    private static boolean hasPathSum(TreeNode root,int sum){
        if (root==null) return false;
        if (root.left==null&&root.right==null&&root.val==sum){
            return true;
        }
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    }

    /*
    迭代 ：https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484927&idx=1&sn=476c0cfc2b04d14fe5c32605a2676b9f&scene=21#wechat_redirect
     */
    private static boolean hasPathSum2(TreeNode root,int sum){

        return false;
    }
}
